Search for: All records

Noisy labels are inevitable in large real-world datasets. In this work, we explore an area understudied by previous works --- how the network's architecture impacts its robustness to noisy labels. We provide a formal framework connecting the robustness of a network to the alignments between its architecture and target/noise functions. Our framework measures a network's robustness via the predictive power in its representations --- the test performance of a linear model trained on the learned representations using a small set of clean labels. We hypothesize that a network is more robust to noisy labels if its architecture is more aligned with the target function than the noise. To support our hypothesis, we provide both theoretical and empirical evidence across various neural network architectures and different domains. We also find that when the network is well-aligned with the target function, its predictive power in representations could improve upon state-of-the-art (SOTA) noisy-label-training methods in terms of test accuracy and even outperform sophisticated methods that use clean labels. 

We study how neural networks trained by gradient descent extrapolate, i.e., what they learn outside the support of the training distribution. Previous works report mixed empirical results when extrapolating with neural networks: while feedforward neural networks, a.k.a. multilayer perceptrons (MLPs), do not extrapolate well in certain simple tasks, Graph Neural Networks (GNNs) – structured networks with MLP modules – have shown some success in more complex tasks. Working towards a theoretical explanation, we identify conditions under which MLPs and GNNs extrapolate well. First, we quantify the observation that ReLU MLPs quickly converge to linear functions along any direction from the origin, which implies that ReLU MLPs do not extrapolate most nonlinear functions. But, they can provably learn a linear target function when the training distribution is sufficiently “diverse”. Second, in connection to analyzing the successes and limitations of GNNs, these results suggest a hypothesis for which we provide theoretical and empirical evidence: the success of GNNs in extrapolating algorithmic tasks to new data (e.g., larger graphs or edge weights) relies on encoding task-specific non-linearities in the architecture or features. Our theoretical analysis builds on a connection of over-parameterized networks to the neural tangent kernel. Empirically, our theory holds across different training settings. 

Most state-of-the-art Graph Neural Networks (GNNs) can be defined as a form of graph convolution which can be realized by message passing between direct neighbors or beyond. To scale such GNNs to large graphs, various neighbor-, layer-, or subgraph-sampling techniques are proposed to alleviate the "neighbor explosion" problem by considering only a small subset of messages passed to the nodes in a mini-batch. However, sampling-based methods are difficult to apply to GNNs that utilize many-hops-away or global context each layer, show unstable performance for different tasks and datasets, and do not speed up model inference. We propose a principled and fundamentally different approach, VQ-GNN, a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. In contrast to sampling-based techniques, our approach can effectively preserve all the messages passed to a mini-batch of nodes by learning and updating a small number of quantized reference vectors of global node representations, using VQ within each GNN layer. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix. We show that such a compact low-rank version of the gigantic convolution matrix is sufficient both theoretically and experimentally. In company with VQ, we design a novel approximated message passing algorithm and a nontrivial back-propagation rule for our framework. Experiments on various types of GNN backbones demonstrate the scalability and competitive performance of our framework on large-graph node classification and link prediction benchmarks. 

Chloroplast genomes have been widely used in studying plant phylogeny and evolution. Several chloroplast genome visualization tools have been developed to display the distribution of genes on the genome. However, these tools do not draw features, such as exons, introns, repetitive elements, and variable sites, disallowing in‐depth examination of the genome structures. Here, we developed and validated a software package called Chloroplast Genome Viewers (CPGView). CPGView can draw three maps showing (i) the distributions of genes, variable sites, and repetitive sequences, including microsatellites, tandem and dispersed repeats; (ii) the structure of the cis‐splicing genes after adjusting the exon‐intron boundary positions using a coordinate scaling algorithm, and (iii) the structure of the trans‐splicing generps12. To test the accuracy of CPGView, we sequenced, assembled, and annotated 31 chloroplast genomes from 31 genera of 22 families. CPGView drew maps correctly for all the 31 chloroplast genomes. Lastly, we used CPGView to examine 5998 publicly released chloroplast genomes from 2513 genera of 553 families. CPGView succeeded in plotting maps for 5882 but failed to plot maps for 116 chloroplast genomes. Further examination showed that the annotations of these 116 genomes had various errors needing manual correction. The test on newly generated data and publicly available data demonstrated the ability of CPGView to identify errors in the annotations of chloroplast genomes. CPGView will become a widely used tool to study the detailed structure of chloroplast genomes. The web version of CPGView can be accessed fromhttp://www.1kmpg.cn/cpgview.